CF1271D Portals

比赛时自己卡在了这题上，现在特来写篇比较符合现场思路的题解

题解：

dp很好想，状态也十分经典：设$f[i][j]$表示前$i$个城堡，手头剩下$j$个士兵的最大收益

初始化$f[0][k]=0$，其它赋为负无穷

从后往前继承状态时要从$a_i$开始枚举（能成功占领的条件），士兵数要减$b_i$（可以加兵的条件）

转移需要稍微思考下

是考虑从每条路转移吗？这样的话就会变得相当复杂，二维状态也不够用了

这时候就需要注意到一条很关键的性质：假设当前要从$u$走路径$$到$v$，那么在合法的前提下，$u$肯定是越大越好

为什么呢？

因为题目有一条很重要的限制，就是$n$座城堡都要被占领，也就是说，既然这条路转移的收益是相同的，而多一个士兵也许能让你占领更多城堡，那么贪心地肯定是要把这个士兵留的时间越长越好

依照这样的思路，我们可以处理出$v_{u,i}$，满足存在边$$，且$u$是连向$v$的最远的一个城堡

由于$v_{u,i}$都是互不干扰的，我们就可以根据收益的从大到小，贪心地在$v_{u,i}$中做选择，注意所做的选择必须是成前缀式的，也就是说要选次优的前提条件是更优的都选了

另外，题目还说可以原地留兵，这怎么搞呢？

我们不妨看成每个城堡上都有一条自环，与其它有着相同终点的路一起比较起点的远近即可

转移部分具体可以看看代码

代码中为了方便理解，最大士兵人数我用的都是常数5000，其实也可以把它换成士兵数的前缀和来减小常数

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=5005;
int ans=-1,a[N],b[N],c[N],link[N],f[N][N],n,m,k,g[N];
vector<int> nxt[N];

inline bool cmp(const int &x,const int &y){
    return c[x]>c[y];
}

signed main(){
    read(n);read(m);read(k);
    for(int i=1;i<=n;i++){
        read(a[i]);
        read(b[i]);
        read(c[i]);
        link[i]=i; //建立自环
    }
    for(int i=1,x,y;i<=m;i++){
        read(x);read(y);
        link[y]=max(link[y],x); //处理出最远起点
    }
    for(int i=1;i<=n;i++)
        nxt[link[i]].push_back(i); //枚举终点，从该点的最远起点连边
    for(int i=1;i<=n;i++)
        sort(nxt[i].begin(),nxt[i].end(),cmp); //按照收益从大到小排序
    memset(f,~0x3f,sizeof f);
    f[0][k]=0; //初始化
    for(int i=1;i<=n;i++){
        for(int j=a[i];j+b[i]<=5000;j++) //继承上个城堡的状态，注意a[i]和b[i]
            f[i][j+b[i]]=f[i-1][j];
        int cnt=nxt[i].size();
        for(int j=0;j<=5000;j++){
            int sum=0;
            g[j]=f[i][j]; //另外开个临时数组g[]，以免覆盖原数组
            for(int k=0;k<cnt;k++) if(j+k+1<=5000){
                sum+=c[nxt[i][k]]; //几个前缀和
                g[j]=max(g[j],f[i][j+k+1]+sum); //k+1是因为k是从0开始的，其实是表示在前缀上选择的城堡的数量（即要花费的士兵的数量）
            }
        }
        memcpy(f[i],g,sizeof g); //赋回去
    }
    for(int i=0;i<=5000;i++)
        ans=max(ans,f[n][i]);
    write(ans);
}